package com.da.javatest.niuke.baodian;

/**
 * @author chenlida
 * @date 2020/10/7 14:53
 * https://www.nowcoder.com/practice/70e00e490b454006976c1fdf47f155d9?tpId=8&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C24LCA {
    public static void main(String[] args) {
        System.out.println(getLCA(20, 18));
        System.out.println(getLCA(33, 71));
    }

    /**
     * 寻找共同祖先，二叉树/2再递归
     */
    public static int getLCA(int a, int b) {
        if (a == b) {
            return a;
        }
        while (a != b) {
            if (a > b) {
                a >>= 1;
            } else {
                b >>= 1;
            }
        }
        return a;
    }
}
